class Solution {
    vector<string> ans;
    string s;
    bool vis[10] = {0};

    void dfs(const string& str) {
        if (s.size() == str.size()) {
            ans.push_back(s);
            return;
        }

        for (int i = 0; i < str.size(); i++) {
            if (i > 0 && str[i] == str[i - 1] && !vis[i - 1]) {
                continue;
            }
            if (vis[i] == false) {
                s.push_back(str[i]);
                vis[i] = true;
                dfs(str);
                s.pop_back();
                vis[i] = false;
            }
        }
    }
  public:
    vector<string> Permutation(string str) {
        if (str.empty()) return {};
        // 排序以便去重
        sort(str.begin(), str.end());
        dfs(str);
        return ans;
    }
};